package com.cn.algorithm02.class05;

import com.cn.algorithm02.class01.CodeUtil;

/***
 * @author: hels
 * @description: 遍历数组，求数组中有多少个数 大于 右边元素的2倍
 *
 * 随机生成的数组是： 44421 = 15
 * -1 1 7 -8 -3 -4 -3
 * 15
 * **/
public class C04_BiggerThanRightTwice {
    public static void main(String[] args) {
        int[] arr = CodeUtil.generatorArray(10, 8, true);
        System.out.println(process(arr, 0, arr.length - 1));
        CodeUtil.printArray(arr);
    }

    public static int process(int[] arr, int L, int R) {
        if (arr == null || L == R) return 0;

        int mid = L + ((R - L)>>1);
        return process(arr, L,mid) + process(arr, mid+1, R) + merge(arr, L, mid, R);
    }

    public static int merge(int[] arr, int L, int mid, int R) {
        int ans = 0;// 求个数
        int right = mid + 1; // 用于记录 数 大于 右边元素的2倍 遍历时的下标
        /*while (left <= mid && right <= R) {
            while (right <= R) {
                if (arr[left] > 2*arr[right++]) {
                    ans++;
                } else {
                    break;
                }
            }
            left++;
            right = mid +1;  // 此处right回退了，因此时间复杂度(N/2)*(N/2) => O(N^2)
        }*/

        // 此处利用单调性，去重冗余比较
        for (int left = L; left <= mid; left++) {
            while (right <= R && arr[left] > arr[right]*2) {
                right++; // 此处right不回退，时间复杂度为O(N)
            }
            ans += right-mid-1; // 2 2 2  1
        }

        int[] sortArr = new int[R-L+1];
        int index = 0;
        int p1 = L, p2 = mid+1;
        while (p1 <= mid && p2 <= R) {
            sortArr[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            sortArr[index++] = arr[p1++];
        }
        while (p2 <= R) {
            sortArr[index++] = arr[p2++];
        }
        for (int i = 0; i < sortArr.length; i++) {
            arr[L++] = sortArr[i];
        }

        return ans;
    }
}